package com.since.algorithm.recursive;

import java.util.Date;

/**
 * Created by Sincerity on 2020/5/03.
 * 描述：8皇后问题 :要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。
 * 规则是皇后能吃掉同一行、同一列、同一对角线的棋子。
 * 1. 暴力for循环解决 {@link #bruteForceAlgorithm()} 大约有5ms的差距
 * 2. 递归  {@link #recursiveAlgorithm(int) }
 * <p>
 * 8. *    *   *   *    *   0   *   *
 * 7. *    *   0   *    *   *   *   *
 * 6. *    *   *   *    *   *   0   *
 * 5. *    0   *   *    *   *   *   *
 * 4. *    *   *   0    *   *   *   *
 * 3. *    *   *   *    *   *   *   0
 * 2. *    *   *   *    0   *   *   *
 * 0. *    *   0   *    *   *   *   *
 * <p>
 * 解决方案:8*8的棋盘要摆放8个皇后，且不能同行同列同对角线，那么每行必定会有一个皇后。
 * 我们可以设一个数组a用来存放每一行皇后的位置，元素值表示第几列（如a[0]=5表示第一行的皇后处于第五个格）。
 * 然后只需要求出数组a的值 问题就解决了，下面介绍三种回溯解法：
 */
class Queen8 {
    private static int count = 0;
    private int max = 10;
    private int[] a = new int[max];

    //首先计算冲突问题
    public static void main(String[] args) {
        Queen8 queen8 = new Queen8();

        //-----开始时间57:37:829 530
        //-----结束时间57:37:868 577
//        queen8.bruteForceAlgorithm(); //大约需要39毫秒
        //-----开始时间00:34:599 675
        //-----结束时间00:34:640 716
//        queen8.recursiveAlgorithm(0); //大约需要41毫秒可以计算

        Date date = new Date();
        System.out.print("-----开始时间" + date.getTime() + "\n");
//        queen8.recursiveAlgorithm(0); //大约需要41毫秒可以计算
//        queen8.bruteForceAlgorithm();
        Date date2 = new Date();
        System.out.print("-----结束时间" + date2.getTime() + "\n");
//        System.out.printf("一共有%d解法", count);
    }

    /**
     * 递归去解决
     *
     * @param n 表示行数
     */
    private void recursiveAlgorithm(int n) {
        for (int j = 0; j < max; j++) {
            //算法的经典所在 获取第j行的值a[n]是j 如0行的值a[0]=0 然后a[0]参与判断是否冲突
            //冲突就开始查找a[0]= 0~7中不冲突的位置参与下面的冲突运算
            a[n] = j;
            if (checkConflict(n)) {//是否冲突 不冲突的情况下 就开始打印或者查找数组的下一位置
                if (n == max - 1) {
                    print();
                } else {
                    recursiveAlgorithm(n + 1);
                }
            }
        }
    }

    /**
     * 打印方法
     */
    private void print() {
        count++;
        System.out.format("第%d种方法的值是:", count);
        for (int k = 0; k < max; k++) {
            System.out.print(+a[k] + " ");
        }
        System.out.println("\n");
    }

    /**
     * 暴力破解法
     * 总结一切数字问题皆可for循环
     */
    private void bruteForceAlgorithm() {
        for (a[0] = 0; a[0] < 10; a[0]++)//第1列
            for (a[1] = 0; a[1] < 10; a[1]++) { //第2列
                if (!checkConflict(1)) continue;
                for (a[2] = 0; a[2] < 10; a[2]++) {//第3列
                    if (!checkConflict(2)) continue;
                    for (a[3] = 0; a[3] < 10; a[3]++) {//第4列
                        if (!checkConflict(3)) continue;
                        for (a[4] = 0; a[4] < 10; a[4]++) {//第5列
                            if (!checkConflict(4)) continue;
                            for (a[5] = 0; a[5] < 10; a[5]++) {//第6列
                                if (!checkConflict(5)) continue;
                                for (a[6] = 0; a[6] < 10; a[6]++) {//第7列
                                    if (!checkConflict(6)) continue;
                                    for (a[7] = 0; a[7] < 10; a[7]++) {//第8列
                                        if (!checkConflict(7)) continue;
                                        for (a[8] = 0; a[8] < 10; a[8]++) {//第9列
                                            if (!checkConflict(8)) continue;
                                            for (a[9] = 0; a[9] < 10; a[9]++) {//第10列
                                                if (!checkConflict(9)) continue;
//                                                   else {
//                                            System.out.format("第%d种解法：\n", t++);
//                                            for (int i = 0; i < 8; i++)
//                                                System.out.format("第%d个皇后：%d\n", i, a[i]);
//                                            System.out.print("\n\n");
//                                        }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
    }

    /**
     * 检测方法 检测第n行的皇后是否与之前的皇后有冲突
     * a、不在同一列：a[i] != a[n]
     * b、不在同一行：因为现在是每一行求一个皇后的位置，所以同一行不会有冲突，不需要考虑
     * c、不在同一对左角线：a[i]-a[n] != i-n
     * d、不在同一右对角线：a[i]-a[n] != -(i-n)
     * 条件c和d可以合成：abs(a[i]-a[n]) != abs(i-n)
     *
     * @param n 行数
     * @return 是否冲突 false 表示冲突
     */
    private boolean checkConflict(int n) {
        for (int i = 0; i < n; i++) {
            //行数冲突                       对角线冲突
            if (a[i] == a[n] || Math.abs(a[i] - a[n]) == Math.abs(i - n)) {
                return false;
            }
        }
        return true;
    }
}
